#include <vector>
using namespace std;

class Solution {
public:
  int nthUglyNumber(int n) {
    int n2, n3, n5, i2, i3, i5;
    n2 = n3 = n5 = 1;
    i2 = i3 = i5 = 0;
    vector<int> res;
    while (res.size() < n) {
      int toAppend = min(min(n2, n3), n5);
      res.push_back(toAppend);
      if (toAppend == n2) {
        n2 = 2 * res[i2++];
      }
      if (toAppend == n3) {
        n3 = 3 * res[i3++];
      }
      if (toAppend == n5) {
        n5 = 5 * res[i5++];
      }
    }
    return res.back();
  }
};
